//https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/?envType=daily-question&envId=2024-03-30

class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        int n = coins.size(), ans = 0, sum = 0;
        sort(coins.begin(), coins.end());
        for(int i = 0; i < n; i++)
        {
            if(sum >= target) return ans;
            while(sum < coins[i] - 1)
            {
                ans++;
                sum = sum * 2 + 1;
            }
            sum += coins[i];
        }
        while(target > sum)
        {
            sum = sum * 2 + 1;
            ans++;
        }
        return ans;
    }
};